package dfsketches.bicycles;

import java.util.Random;

public class BicycleQueue {

	public BicycleQueue(int size) {
		queue = new int[size];
		start = finish = 0;	
	}
	
	public void push(int v) {
		queue[finish++] = v;
		if (finish == queue.length) finish = 0;
		if (finish == start) increaseSize();
	}
	
	public int pop() {
		int result = queue[start++];
		if (start == queue.length) start = 0;
		return result;
	}
	
	public int top() {
		return queue[start];
	}
	
	private void increaseSize() {
		int newSize = queue.length * 2 + 1;
		int[] temp = new int[newSize];
		int i = start++;
		int j = 0;
		while (j < queue.length) {
			temp[j] = queue[i];
			i++;
			if (i == queue.length) i = 0;
			j++;
		};
		queue = temp;
	}
	
	public void clear() {
		start = finish = 0;	
	}
	
	public boolean isEmpty() {
		return start == finish;
	}
	
	public void shuffle(Random rnd) {
		int end = queue.length;
		if (finish >= start) {
			int capacity = finish - start;
			for (int i = start; i < finish; i++) {
				int swap = rnd.nextInt(capacity) + start;
				int temp = queue[i];
				queue[i] = queue[swap];
				queue[swap] = temp;
			}
		} else {
			int capacity = finish + end - start;
			for (int i = start; i < end; i++) {
				int swap = (rnd.nextInt(capacity) + start) % end;
				int temp = queue[i];
				queue[i] = queue[swap];
				queue[swap] = temp;
			}
			for (int i = 0; i < finish; i++) {
				int swap = (rnd.nextInt(capacity) + start) % end;
				int temp = queue[i];
				queue[i] = queue[swap];
				queue[swap] = temp;
			}
		}
	}

	public int size() {
		if (finish >= start) {
			return finish - start;
		} else {
			return finish + queue.length - start;
		}
	}
	
	private int[] queue;
	private int start;
	private int finish;
}